package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-07-26 20:43
 */
public class Test10_复杂链表的复制 {


    /**
     * 题目：
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
     * 每个节点除了有一个 next 指针指向下一个节点，
     * 还有一个 random 指针指向链表中的任意节点或者 null。
     * <p>
     * 思路：
     * 拼接+分割
     */


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copy(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        //在原有节点上复制各个节点
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        //构建复制的那一份节点的random
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //现在只需要将链表拆分为两份就可以了
        cur = head.next;
        Node pre = head;
        Node res = head.next;
        // pre代表原来的链表 res代表复制的链表
        while (cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;//最后一元素的next被复制的链表给占了，手动补全
        return res;
    }
}
